package com.leetcode2;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

import com.structure.TreeNode;

public class Index297Codec {
	String NULL = "#",SEP = ",";
    StringBuilder b = new StringBuilder();
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null){
            b.append(NULL).append(SEP);
            return null;
        }
        b.append(root.val).append(SEP);
        serialize(root.left);
        serialize(root.right);
        return b.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
    	 if(data == null) return null;
    	LinkedList<String> nodes = new LinkedList<>();
        String [] t = data.split(SEP);
        for(int i = 0;i < t.length - 1;i ++){
            nodes.add(t[i]);
        }
        return deserialize(nodes);
    }

    public TreeNode deserialize(LinkedList<String> nodes){
        if(nodes.isEmpty()) return null;
        
        String node = nodes.removeFirst();
        if(node.equals(NULL)) return null;
        TreeNode root = new TreeNode(Integer.valueOf(node));
        root.left = deserialize(nodes);
        root.right = deserialize(nodes);
        return root;
    }
}
